.Sec(Symbolic Expressions,Symbolic expressions)
.SS(Introduction)
.begin "int"
.FP
This book is a study of data structures and programming languages;
in particular it is a study of data structures and programming
languages centered around the language LISP.⊗↓However, this is not 
a manual to help you become a proficient LISP coder.←
We will study many of the formal and theoretical aspects of languages  and
data structures as well as examining the practical applications of
data structures. We will show that this area of computer science
is a discipline of importance and beauty, worthy of careful study.
How are we to proceed?⊗↓How do we introduce rigor into a field
whose countenance is as %3ad hoc%* and diverse as that of programming?
We must bear in mind that the results of our studies are to have
practical applications.←
We must not pursue theory and rigor without proper
regard for practice. Our study is not that of pure mathematics; our
results will have applications in everyday programming practice.

Number theory studies properties of a certain class of operations definable
over the set %dN%* of non-negative integers also called natural numbers.
A very formal presentation might begin with a construction of %dN%*
from more primitive notions, but it is usually assumed that the reader
is familiar with the fundamental properties of %dN%*.
In either case the next step would be to define the
class of operations which we would allow on our domain.

For most people and most purposes,  the following  characterization of a natural number
is satisfactory:

.BEGIN TABIT1(5);
.pt24
%2I%* \A natural number is a sequence of decimal digits.
.pt24
.END
.FP
The definition assumes the terminology of "sequence", "decimal" and "digit"
are known. If any of these terms are %6not%1 understood, they can be
further elaborated. However, this process of explanation and description
must terminate. We must assume that some concepts require no further
elaboration. The current definition suffers from a different kind of
inadequacy. It fails to  illuminate
the relationships between natural numbers.
The "meaning" of the natural numbers is missing. It is
like giving a person an alphabet and rules for forming syntactically
correct words but not supplying  a dictionary which relates these words to
the person's vocabulary.

If pressed for details we might attempt a more elaborate
characterization like the following:
.pt24;
.BEGIN GROUP;
.ONCE indent 5,5
%21.%* %3zero%* is an element of %dN%*.
.ONCE indent 0,5;
%2II%*###%22.%* If %3n%* is in %dN%* then  the %3successor%* of %3n%* is in %dN%*.
.ONCE indent 5,5
.SELECT 1;
%23.%* The only elements of %dN%* are those created by finitely many applications 
of rules %21%* and %22%*.
.pt24
.END
.FP

We can  define %3successor%* as a specific mapping, %2S%1,
which creates new elements subject to the rules that
two elements, %3x%1 and %3y%1 are equal just in the case that
%2S%3(x)%1 equals %2S%3(y)%1; and %2S%3(x)%1 is different from %3x%1, for any
element %3x%1.
We select a distinguished element, %30%*, as a
notation for %3zero%*; and   abbreviate %2S%3(0)%1 as %31%1, 
and abbreviate %2S%3(%2S%3(0))%1 as %32%1
etc. in the usual manner.

Given a choice between the two previous definitions, %2I%* and %2II%*, 
it appears that %2II%* is more precise.
Much less is left to the imagination; given
%3zero%* and a definition of %3successor%* the definition will act as a
recipe for producing elements of %dN%*. This style of definition is called an
⊗→inductive definition↔← or ⊗→generative definition↔←.

.BEGIN "x1" GROUP;
.P117:
The basic content of an inductive definition
of a set of objects consists of three parts: 
.BEGIN INDENT 10,10;
.PT24;
(1) A description of an initial set of objects; the elements of this
set are the initial elements of the set we are describing in the
inductive definition.
.END
.fp;
%2IND%*
.BEGIN indent 10,10;
(2) Given the description of some existing elements
in the set, we are given a means of constructing more elements.  
.PT2;
(3) A termination clause, saying that the only elements in the set are those
which gained admittance by either (1) or (2).
.END
.END "x1"
.PT24;
.FP
Notice that our definition of %dN%*, in terms of %3zero%* and %3successor%*,
is an instance of %2IND%*: we are defining the set of natural numbers:
%3zero%* is initially included in the set; then applying the second phrase
of the definition we can say that %3one%* is in the set since %3one%* is the
successor of  %3zero%*.

We can recast the positional notation description as an inductive definition.

.BEGIN GROUP;
.PT24;
.NL;
%21.%*##A digit is a numeral.
.NL;
%22.%*##If %3n%* is a numeral then %3n%* followed by a digit is a numeral.
.NL;
%23.%1##The only numerals are those created by finitely many applications of %21%* and %22%*.
.END
.PT24;
.FP;
In words, "a numeral is a digit, or a numeral followed by a digit".

In this application of %2IND%*, the initial set has more
than one element; namely the  ten decimal digits.
Again, we assume that the questioner knows what "digit" means.
This is a characteristic of all definitions:
we must stop %6somewhere%* in our explication. 
Notice too that we assume  that "followed by" means juxtaposition.


Inductive definitions  have been the province of mathematics for
many years; however, computer science has 
developed a style of syntax specification 
called BNF (Backus-Naur Form) equations which has the same intent as
that of inductive definitions.  Here is the previous inductive definition
of "numeral" as a set of BNF equations:

.BEGIN TABIT1(15);
.BOXA
.ONCE  INDENT 0
<numeral>\::= <digit>
.PT2
<numeral>\::= <numeral><digit>
.FP
As an abbreviation, the  two BNF equations may also be written:
.ONCE INDENT 0;
<numeral>\::= <digit> | <numeral><digit>.
.BOXB
.END
.FP
A comparison between the BNF and the inductive descriptions of
"numeral"  should clarify much of the notation, but
we will give a more detailed analysis.
The symbol "::=" may be read "is a",
the symbol "|" may be read "or".
The character strings beginning with "<" and ending with ">" correspond to
"numeral" and "digit" in %21%1 and %22%*;
by convention, components of BNF equations which %6describe%* elements
are enclosed in "<" and ">"; and elements  which are given %6explicitly%*
are written without the "< >" fence.
Thus "<digit>" is not a numeral but is a description; to make the definition
of <numeral> complete we should include an equation like:

.BEGIN TABIT1(15);
.BOXA
<digit>\:: = %30 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9%*
.BOXB
.END
.FP
Juxtaposition of objects implies concatenation of the syntactic objects. Thus
"89" is an instance of "<numeral><digit>".


We  have also introduced the  difference  between an  abstract
object  and  a  representation for that object.    
This  distinction has  been  well
studied in philosophy and mathematics, and we will see that this idea
has strong consequences  for the field of  programming  and computer
science.  Abstract objects  and their representations will play 
crucial roles in this text. 
.<<COMPLIS AND FIENDS>>
.GROUP
.FP
With this introduction, here is %3complis%* and
friends:
.BOXA
.fp
%3complis <= λ[[u;off;vpl] complis%9'%*[u;off;off;vpl;();();();1]%1
.APART
.BOXA
.BEGIN turn on "\"; no fill;TABs 16,27,40;SELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 12,20,30;SELECT 3;TURN OFF "←";>>
.KRK
.GROUP
complis%9'%* <= λ[[u;org;off;vpl;triv;cmplx;pop;ac]
\[null[u] →\[null[cmplx] → triv;
\\ %et%* → append\[rest[cmplx];
\\\ list[mkmove[mem[first[pop]];1]];
\\\ rest[pop];
\\\ triv]];
.PT2;
.END
.BEGIN turn on "\"; no fill;TABs 16,27,46,67;SELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 12,23,36,63;SELECT 3;TURN OFF "←";>>
.GROUP
.KRK
\ isconst[first[u]] → complis%9'%*[\rest[u];
\\\org;
\\\off;
\\\vpl;
\\\concat[mkconst[ac;first[u]];triv];
\\\cmplx;
\\\pop;
\\\add1[ac]];
.PT2
.END
.BEGIN turn on "\"; no fill;TABs 16,27,44,51,58;SELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 12,23,33,63;SELECT 3;TURN OFF "←";>>
.KRK
.GROUP
\ isvar[first[u]] → complis%9'%*[\rest[u];
\\\org;
\\\off;
\\\vpl;
\\\concat[\mkvar[\ac;
\\\\\loc[first[u];off;vpl]];
\\\\triv];
\\\cmplx;
\\\pop;
\\\add1[ac]];
.PT2
.END
.BEGIN turn on "\"; no fill;TABs 16,27,47,56,76;sELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 16,27,47,56,70;SELECT 3;TURN OFF "←";>>
.GROUP
.KRK
\ iscarcdr[first[u]] → complis%9'%*[\rest[u];
\\\org;
\\\off;
\\\vpl;
\\\append[\reverse[compcarcdr[\ac;
\\\\\ first[u];
\\\\\ off;
\\\\\ vpl]];
\\\\triv];
\\\cmplx;
\\\pop;
\\\add1[ac]];
.PT2
.END
.BEGIN turn on "\"; no fill;TABs 16,28,45,54,61,70,76;SELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 16,28,45,54,61,70,72;SELECT 3;TURN OFF "←";>>
.KRK
.GROUP
\ iscond[first[u] → complis%9'%*[\rest[u];
\\\org;
\\\sub1[off];
\\\vpl;
\\\triv;
\\\append[\cmplx;
\\\\concat[\mkpush[1];
\\\\\comcond[\args%4c%3[\first[u]];
\\\\\\gensym[];
\\\\\\off;
\\\\\\vpl]]];
\\\concat[mkpop[ac];pop];
\\\add1[ac]];
.PT2
.END
.BEGIN turn on "\"; no fill;TABs 16,31,40,47,65,74;SELECT 3;TURN OFF "←";
.<<BEGIN turn on "\"; no fill;TABs 12,23,30,36,50,57;SELECT 3;TURN OFF "←";>>
.GROUP
.KRK
\ %et%* → complis%9'%*[\rest[u];
\\org;
\\sub1[off];
\\vpl;
\\triv;
\\append[\cmplx;
\\\concat[\mkpush[1];
\\\\λ[[z] compapply[\func[first[u]];
\\\\\complis[\z;
\\\\\\off;
\\\\\\vpl];
\\\\\length[z]]]
\\\\ [arglist[first[u]] ]];
\\concat[mkpop[ac];pop];
\\add1[ac]]]
.BOXB
.END

.BEGIN CENTERIT;SELECT 3;
.PT2
mkmove <= λ[[ac;loc][eq[ac;loc] → (); %et%* → list[MOVE;ac;loc]]]
.END

.BEGIN TABS 10,19,31,54;NOFILL;SELECT 3;TURN OFF "←";GROUP;TURN ON"\";
.<<BEGIN TABS 6,15,24,42;NOFILL;SELECT 3;TURN OFF "←";GROUP;TURN ON"\";>>
.BOXA
.KRK
compcarcdr <= λ[[ac;exp;off;vpl]
\\[isvar[arg[exp]] → list[mkcarcdr[\func[exp];
\\\\ac;
\\\\loc[arg[exp];off;vpl]]]
\\%Et%* → concat[\mkcarcdr_ac[func[exp];ac;ac];
\\\compcarcdr[ac;arg[exp];off;vpl]]]]
.BOXB
.APART
.GROUP
iscarcdr <=λ[[u]\[iscar[u] →iscarcdr[arg[u]]
\\ iscdr[u] →iscarcdr[arg[u]]
\\ atom[u] → or[isvar[u];isconst[u]];
\\ %et%* → %ef%* ]]
.BOXB
iscar <= λ[[x] eq[func[x];CAR]]
.PT2
iscdr <= λ[[x] eq[func[x];CDR]]
.PT2
mkcarcdr <=λ[[carcdr;ac;loc] list[carcdr;ac;loc]]
.END

.end "int"